package Alibaba;

/**
 * @author zhangmin
 * @create 2022-01-30 14:38
 * 37. 解数独
 * 编写一个程序，通过填充空格来解决数独问题。
 * 数独的解法需 遵循如下规则：
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * 回溯：
 * 路径：已经选择好的位置
 * 选择列表：0-9中合法的数字
 * 终止条件：r==m最后一行已遍历完，整个数独结束
 */
public class solveSudoku37 {
    //判断board[r][c]是否可以放入n
    boolean isValid(char[][] board,int r,int c,char n){
        for (int i = 0; i <9 ; i++) {
            //判断行是否重复
            if (board[r][i]==n) return false;
            //判断列是否重复
            if (board[i][c]==n) return false;
            //判断小方格内是否重复
            if (board[(r/3)*3+i/3][(c/3)*3+i%3]==n) return false;
        }
        return true;
    }

    boolean backtrack(char[][] board,int i,int j){
        int m=board.length,n=board[0].length;
        if (j==n){
            //穷举到最后一列，则换到下一行开始
            return backtrack(board,i+1,0);
        }
        if (i==m){
            //遍历完最后一行了
            return true;
        }
        if (board[i][j]!='.'){
            return backtrack(board,i,j+1);
        }
        for (char k = '1'; k <='9' ; k++) {
            if (!isValid(board,i,j,k)) continue;
            board[i][j]=k;
            if (backtrack(board,i,j+1)){
                return true;
            }
            board[i][j]='.';
        }
        return false;
    }
    public void solveSudoku(char[][] board) {
        backtrack(board,0,0);
    }
}
